import java.util.LinkedList;
import java.util.Queue;

public class HuffmanTree {
	
	private HuffmanNode root;
	private EndOfCode endOfCode;
	
	public HuffmanTree() {
		this.root = new NotYetTransmitted();
		this.endOfCode = new EndOfCode();
		insertSymbol(root, endOfCode);
	}

	public BitSequence encode(String text){
		
		BitSequence encodedText = new BitSequence();
		for(int i = 0; i < text.length(); i++){
			encodedText.append(transformSymbol(text.charAt(i)));
		}
		return encodedText;
	}
	
	public void addEndOfCode(BitSequence bs){
		bs.append( getPath(endOfCode) );
	}
	
	public String decode(BitSequence bitSeq)
	{
		String decodedText = new String();
		
		HuffmanNode curNode = root;
		while(!(curNode instanceof EndOfCode)){
			
			/* Found the nyt, it means that the new 8 bit is a symbol*/
			if(curNode instanceof NotYetTransmitted){
				char c = bitSeq.pollChar();
				insertSymbol(curNode, new HuffmanNode(c));
				decodedText += c;
				curNode = root;
			}
			
			/* Navigate through the tree */
			if(bitSeq.pollBit()) curNode = curNode.getRightNode();
			else curNode = curNode.getLeftNode();
			
			/* Found a leaf, so get the symbol */
			if(curNode.getSymbol() != null)
			{
				decodedText += curNode.getSymbol();
				updateTree(curNode);
				curNode = root;
			}
		}		
		
		return decodedText;
	}
	
	private BitSequence transformSymbol(char symbol)
	{
		Queue<HuffmanNode> queue = new LinkedList<HuffmanNode>();
		queue.add(root);
		
		while(!queue.isEmpty())
		{
			HuffmanNode curNode = (HuffmanNode) queue.poll();
			
			if(curNode instanceof NotYetTransmitted){
				BitSequence nytPath = null;
				if( curNode != root )
					nytPath = getPath(curNode);
				else
					nytPath = new BitSequence();
				
				insertSymbol(curNode, new HuffmanNode(symbol));
				nytPath.addLast(symbol);
				return nytPath; // + symbol ASCII
			} 
			
			if(curNode.getSymbol() != null){
				if(curNode.getSymbol().charValue() == symbol)
				{	
					BitSequence path = getPath(curNode);
					updateTree(curNode);
					return path;
				}
			}
			
			if(curNode.getRightNode() != null) queue.add(curNode.getRightNode());
			if(curNode.getLeftNode() != null)  queue.add(curNode.getLeftNode());
		}
		return null;
	}	
	
	private void insertSymbol(HuffmanNode nyt, HuffmanNode symbolNode)
	{
		HuffmanNode fatherNode = new HuffmanNode();
		symbolNode.setFatherNode(fatherNode);
		fatherNode.setRightNode(symbolNode);
		
		fatherNode.setLeftNode(nyt);
		
		fatherNode.setFatherNode(nyt.getFatherNode());
		
		//Caso esteja adicionando no root
		if( nyt.getFatherNode() != null )
			nyt.getFatherNode().setLeftNode(fatherNode);
		else
			root = fatherNode;
		
		nyt.setFatherNode(fatherNode);
		
		updateTree(fatherNode);
	}
	
	private void updateTree(HuffmanNode starterNode){
		/* upNode is the node that is being updated */
		HuffmanNode upNode = starterNode;
		upNode.increasePriority();
		
		while(upNode != root)
		{			
			HuffmanNode curNode = root;
			Queue<HuffmanNode> queue = new LinkedList<HuffmanNode>();
			queue.add(curNode);
			
			while(curNode != upNode)
			{
				curNode = queue.poll();

				if(curNode.getPriority() < upNode.getPriority())
				{
					HuffmanNode tmpFather = curNode.getFatherNode();
					curNode.setFatherNode(upNode.getFatherNode());
					upNode.setFatherNode(tmpFather);
					
					if( upNode.getFatherNode() != null ){
						if(upNode.getFatherNode().getLeftNode() == curNode ) upNode.getFatherNode().setLeftNode(upNode);
						else if(upNode.getFatherNode().getRightNode() == curNode) upNode.getFatherNode().setRightNode(upNode);
						if(curNode.getFatherNode().getLeftNode() == upNode) curNode.getFatherNode().setLeftNode(curNode);
						else if(curNode.getFatherNode().getRightNode() == upNode) curNode.getFatherNode().setRightNode(curNode);
						break;
					}else
						break;
				}
				if(curNode.getRightNode()!=null) queue.add(curNode.getRightNode());
				if(curNode.getLeftNode()!=null) queue.add(curNode.getLeftNode());
			}			
			upNode = upNode.getFatherNode();
			upNode.increasePriority();
		}
	}
	
	private BitSequence getPath(HuffmanNode startNode){
		BitSequence returnBS = new BitSequence();
		HuffmanNode curNode = startNode;
		while(curNode != root){
			boolean b = curNode.getFatherNode().getRightNode() == curNode;
			returnBS.addLast(b);
			curNode = curNode.getFatherNode();
		}
		return returnBS;
	}
}
